The invention relates to a method and an apparatus for determining a route for a navigation system and/or a driver assistance system. The invention also relates to a method for determining correction values for a route calculation algorithm and to a system which includes the apparatus for determining the route.
In vehicle navigation systems, the so-called A* algorithm is used in many cases to calculate the route. This algorithm is used to calculate a shortest path between a starting node and one or more arbitrary nodes in a graph with a positive edge weight. In graph theory, a graph is a set of points, the points partially being connected to one another by means of so-called edges. The points are also called nodes. The edges are also referred to as lines or connections. The shape of the points and edges does not play a role in graph theory. In graph theory, a real number assigned to the respective edge is referred to as the edge weight. The real number may represent, for example, a distance, a time period or a gasoline consumption.
The A* algorithm uses an estimation function (heuristics) in order to search in a targeted manner and therefore to reduce the run-time. However, if the estimation function does not represent the real route and/or path conditions in an area with sufficient accuracy, the calculation of the optimum route may take a very long time.
The object on which the invention is based is to provide a method and an apparatus for determining a route, a method for determining correction values for a route calculation algorithm and a system which contribute to increasing efficiency of the route determination, in particular accelerating the route determination.
According to a first and a second aspect of the invention, a method and a corresponding apparatus for determining a route for a navigation system and/or a driver assistance system are provided. The navigation system and/or driver assistance system is assigned at least one storage unit for storing digital map data for a route network and/or path network in a predefined area. In this case, the digital map data include respective nodes in the area and connections between the respective nodes in the area. The digital map data also include respective edge costs for the respective connections between the nodes and predefined correction values for the respective nodes. The route from a predefined starting node to a predefined destination node is determined on the basis of the digital map data stored in the storage unit in such a manner that, for a possible expansion of a respective current node, total costs are determined for the current node on the basis of a sum of edge costs of an optimum route from the starting node to the current node and a destination-node-based heuristic value for the current node, which represents respectively estimated costs from the current node to the destination node, and a predefined destination-node-based correction value. In this case, the destination-node-based correction value is representative of a mean value of cost ratios of respective nodes in a predefined set, the respective cost ratios being dependent on the edge costs of the connections, which lie between the current node and the respective node in the set and represent an optimum route between the current node and this node in the set, and a heuristic value for the current node with respect to this respective node in the set.
Data relating to the determined route can be forwarded to the navigation system for optically and/or acoustically signaling the determined route, for example on a display, and/or for determining and outputting driving instructions. Additionally or alternatively, the data may be forwarded to the driver assistance system, the predefined driver assistance system being designed to control predefined vehicle functions of a vehicle on the basis of the determined data relating to the route.
The respective cost ratio is a direct measure of a discrepancy between the heuristic value for the current node with respect to the respective node in the set and the sum of the edge costs of an optimum route from the current node to the respective node in the set.
The destination-node-based heuristic value can be assessed, for example, using the destination-node-based correction value. For example, if the destination-node-based heuristic value does not represent the real route and/or path conditions in the area with sufficient accuracy, the destination-node-based heuristic value may have an excessively small value. This can be at least partially compensated for by means of the assessment using the destination-node-based correction value. In comparison with the determination of the route without correction values, the optimum route can be determined with considerably fewer calculation steps when using the correction values.
The sets of nodes for which respective correction values are predefined may include a different number of nodes depending on the requirements. An additionally required need for storage space for storing the correction values can therefore be kept suitably low.
The edge costs and the estimated costs have a predefined correspondence. The edge costs represent a value of a weighting function. The weighting function weights respective individual edge costs of the respective connection, for example route length costs and/or journey time costs, in a predefined manner. The estimated costs represent the value of an estimation function which weights estimated individual costs, for example estimated route length residual costs from a current node to the destination node and/or estimated journey time residual costs from the current node to the destination node, in a predefined manner similar to the weighting function. In a simplified case, the edge costs may represent, for example, the route length costs of the respective connection and the estimated costs may represent, for example, the estimated route length residual costs, for example the Euclidean distance, between the current node and the destination node.
The optimum route is optimum with respect to the edge costs. The destination-node-based correction values are at least one subset of the predefined correction values.
Expanding a node means that, starting from this node, the total costs of further nodes having a connection to this node are determined.
The route can be determined, for example, according to an A* algorithm. In the A* algorithm, the node having the lowest total costs is respectively expanded next. For the decision regarding whether the current node is expanded in the next step, the total costs of the current node are determined and compared with the total costs of further possible expansion nodes.
In one advantageous refinement of the first and second aspects of the invention, the digital map data include the respective positions of the nodes, and the destination-node-based heuristic value is determined on the basis of the position of the current node and the position of the destination node. A storage capacity of the storage unit can therefore be advantageously kept low.
In another advantageous refinement of the first and second aspects of the invention, the digital map data includes predefined heuristic values for the respective nodes with respect to the respective other nodes in the area which each represent estimated costs from one node in each case to the other node in each case, and the destination-node-based heuristic value is therefore predefined. This advantageously makes it possible to save computing capacity since the destination-node-based heuristic values can be determined in advance and therefore independently of a current route calculation.
In another advantageous refinement of the first and second aspects of the invention, the respective destination-node-based heuristic value represents the Euclidean distance between the current node and the destination node. The destination-node-based heuristic values can therefore be advantageously determined in a very simple manner; in particular, the required data are already available in the storage unit. Furthermore, the Euclidean distance to the destination is a monotonous estimation function (heuristics) and therefore complies with, in particular, the reliability prerequisite for the A* algorithm.
In another advantageous refinement of the first and second aspects of the invention, the heuristic value for the current node with respect to the respective node in the set represents the Euclidean distance between the current node and this respective node in the set. The heuristic values can therefore be advantageously determined in a very simple manner.
In another advantageous refinement of the first and second aspects of the invention, the area is subdivided into a plurality of segment regions, and the predefined set of nodes includes selected nodes which are arranged in a destination node segment region which includes at least the destination node. This advantageously makes it possible to predefine the correction values with sufficient accuracy, with the result that the route can be determined more efficiently. Alternatively, the predefined set of nodes may also include all nodes arranged in a destination node segment region. The selected nodes can be selected stochastically and/or on the basis of at least one predefined rule, for example.
In another advantageous refinement of the first and second aspects, the mean value of the cost ratios of the nodes in the set represents an arithmetic mean value of the cost ratios. This has the advantage that the respective correction values can be easily provided.
In another advantageous refinement of the first and second aspects, the respective segment region of the area includes a predefined radius region starting from the current node and a predefined angle region around the current node. This has the advantage that the respective correction values can be easily provided.
According to a third aspect of the invention, a method is provided for determining correction values for a route calculation algorithm on the basis of digital map data for a route network and/or path network in a predefined area. In this case, the digital map data include respective nodes in the area and connections between the respective nodes in the area. The digital map data also include respective edge costs for the respective connections between the nodes. At least one reference set of nodes is predefined for at least some of the nodes in the area for the respective node. A cost ratio for the respective node in the reference set is determined for the respectively predefined reference set of nodes. This cost ratio is determined on the basis of the edge costs of the connections, which lie between the node, for which the correction value is determined, and the respective node in the reference set and represent an optimum route between the node, for which the correction value is determined, and the node in the reference set, and the heuristic value for the node, for which the correction value is determined, with respect to the node in the reference set. A mean value is determined on the basis of the determined cost ratios of the nodes in this reference set, and the respective correction value is determined on the basis of the mean value.
Advantageous refinements of the first and second aspects also apply in this case to the third aspect.
The correction values can be advantageously determined independently of current route determination, for example during map compiling.
The heuristic value is determined using an estimation function which is also called heuristics. The estimation function may include, for example, a function for determining a shortest distance between two points in a predefined two-dimensional coordinate system (Euclidean distance). The prerequisite for the A* algorithm is that the estimation function is permissible. The estimation function is permissible if the respective heuristic value does not exceed the respective sum of the edge costs of the connections of the optimum route between two nodes to be considered. That is to say, the respective heuristic value must always be in the range [0; w] if w respectively denotes the sum of the edge costs of the connections of the optimum route between the two nodes to be considered.
The respective correction values can therefore be determined on the basis of adapted mean values if necessary, with the result that it can be ensured that the permissibility prerequisites of the A* algorithm are also complied with when using the correction values. For example, the respective mean values can be adapted by dividing them by a predefined factor which is greater than 1.
In one advantageous refinement of the third aspect, the digital map data include the respective positions of the nodes, and the heuristic value for the node, for which the correction value is determined, with respect to the respective node in the reference set is determined on the basis of the position of the node, for which the correction value is determined, and the position of the respective node in the reference set. This advantageously makes it possible to save storage capacity.
In another advantageous refinement of the third aspect, the digital map data include predefined heuristic values for the respective nodes with respect to the respective other nodes in the area which each represent estimated costs from one node in each case to the other node in each case, and the heuristic value for the node, for which the correction value is determined, with respect to the respective node in the reference set is therefore predefined. This advantageously makes it possible to save computing capacity when calculating the correction values.
In another advantageous refinement of the third aspect, the heuristic value for the node, for which the correction value is determined, with respect to the node in the reference set represents the Euclidean distance between the node, for which the correction value is determined, and the node in the reference set. This makes it possible to easily determine the correction values.
In another advantageous refinement of the third aspect, the area is subdivided into a plurality of segment regions starting from the respective node for which the correction values are calculated, and selected nodes in the respective segment regions each form one of the predefined reference sets of nodes. This has the advantage that the respective correction values can be easily determined. Alternatively, the respective predefined reference set may also include all nodes which are arranged in the respective segment region. The selected nodes may be selected stochastically and/or on the basis of at least one predefined rule, for example. All nodes arranged in the respective segment region are assigned the correction values which have been determined for this respective segment region.
In another advantageous refinement of the third aspect, the predefined segment regions of the area each include a predefined radius region starting from the respective node, for which the correction values are determined, and a predefined angle region around this node for which the correction values are determined. This has the advantage that the respective correction values can be easily determined.
According to a fourth aspect of the invention, a system is provided which has a storage unit and an apparatus according to the second aspect and in which the storage unit stores digital map data for a route network and/or path network in a predefined area. The apparatus is coupled to the storage unit using signaling and is designed to read the digital map data from the storage unit. In this case, the digital map data include respective nodes in the area and connections between the respective nodes in the area. Furthermore, the digital map data include predefined correction values for the respective nodes.
Advantageous refinements of the first and second aspects also apply in this case to the fourth aspect.
Other objects, advantages and novel features of the present invention will become apparent from the following detailed description of one or more preferred embodiments when considered in conjunction with the accompanying drawings.